namespace Algorithms
{
	public class SearchingAlgorithms
	{
		// Linear search - Линейный поиск
		// Наихудшее время работы - n (если элемента нет в массиве)
		// Наилучшее время работы - 1 (если элемент самый первый)
		// - наибольшее время работы среди алгоритмов поиска
		// + единственное решение, если ничего неизвестно о порядке элементов
		// Поочередно проходим по массиву сравнивая элемент с искомым.
		// В случае совпадения возвращаем индекс, если дошли до конца, возвращаем -1
		public static int LinearSearch(int[] arr, int elem)
		{
			int index=-1;
			for (int i=0; i<arr.Length; i++) 
			{
				if (arr [i] == elem) 
				{
					index = i;
					break;
				}
			}
			return index;
		}

		// Binary search - Двоичный поиск (loop implementation)
		// Наихудшее время работы - lg(n)
		// Наилучшее время работы - 1
		// - массив должен быть изначально отсортирован (на что может уйти время n lg(n))
		// + если известно заранее, что массив уже отсортирован, это один из наилучших способов поиска
		// Находим средний элемент массива и сравниваем с искомым элементом. ( middleIndex=(startIndex+endIndex)/2 )
		// Если они равны - возвращаем индекс среднего элемента
		// Если искомый меньше среднего -повторяем процедуру для левой части (0 -> middleIndex-1)
		// Если искомый элемент больше среднего - рассматриваем правую часть (middleElement+1 -> arr.Length-1)
		// Повторяем процедуру пока не найдем элемент либо пока рассматриваемый массив не окажется пустым.
		public static int BinarySearch(int[] arr, int elem)
		{
			int startIndex = 0;
			int endIndex = arr.Length - 1;
			while (startIndex<=endIndex) {
				int middleIndex = (startIndex + endIndex) / 2;
				if (arr [middleIndex] == elem)
					return middleIndex;
				if (arr [middleIndex] < elem) {
					startIndex = middleIndex + 1;
					continue;
				}
				if (arr [middleIndex] > elem) {
					endIndex = middleIndex - 1;
					continue;
				}
			}
			return -1;
		}
        public static int RecursiveBinarySearch(int[] arr, int startIndex, int endIndex, int elem)
        {
            if (endIndex < startIndex)
                return -1;
            int middleIndex = (startIndex + endIndex)/2;
            if (arr[middleIndex]==elem)
                return middleIndex;
            if (arr[middleIndex] < elem)
            {
                startIndex = middleIndex + 1;
            }
            if (arr[middleIndex] > elem)
            {
                endIndex = middleIndex - 1;
            }
            return RecursiveBinarySearch(arr, startIndex, endIndex, elem);
        }

        public static int RecursiveBinarySearch(int[] arr, int elem)
        {
            return RecursiveBinarySearch(arr, 0, arr.Length-1, elem);
        }

        public static void MyConstrainedCopy(int[] oldArr, int srcIndex, int[] newArr, int  dstIndex){
            int i=0;
            int j = srcIndex;
            for (; i<newArr.Length; ++i, ++j)
                newArr [i] = oldArr [j];
        }
    }
}